package com.leetcode;

import java.util.Scanner;

/**
 * @author Dennis Li
 * @date 2020/9/2 21:02
 */
public class EditDistance {

    // 字符串的问题一般会从字符串的末端向前进行遍历来解决
    public static void main(String[] args) {
        final Scanner scanner = new Scanner(System.in);

        while (scanner.hasNext()) {
            String str1 = scanner.nextLine();
            String str2 = scanner.nextLine();
            distance(str1, str2);
        }
    }

    private static void distance(String str1, String str2) {
        final int m = str1.length(), n = str2.length();

        final int[][] dp = new int[m + 1][n + 1];

        for (int i = 0; i <= m; i++) {
            // 每一位都不相同，那么有多少位就要修改多少位
            dp[i][0] = i;
        }

        for (int j = 0; j <= n; j++) {
            //同理
            dp[0][j] = j;
        }

        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (str1.charAt(i - 1) == str2.charAt(j - 1))
                    // 如果相同，那么就继续向前寻找
                    dp[i][j] = dp[i - 1][j - 1];
                else {
                    // 从三种修改方式中取最小值
                    dp[i][j] = min(dp[i - 1][j] + 1, dp[i][j - 1] + 1, dp[i - 1][j - 1] + 1);
                }
            }
        }

        System.out.println(dp[m][n]);
    }

    private static int min(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }

}
